{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Chapter 4 Solutions"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Question 1\n",
    "### Laplace expansion\n",
    "We have $\\det A = 1(4\\cdot4-6\\cdot2) - 3(2\\cdot 4 - 6\\cdot 0) + 5(2\\cdot 2-4\\cdot 0) = 0$.\n",
    "### Sarrus rule\n",
    "We have $\\det A = 1\\cdot 4 \\cdot 4 + 2\\cdot 2\\cdot 5 + 0\\cdot 3\\cdot 6 - 5\\cdot 4\\cdot 0 - 6\\cdot 2\\cdot 1 - 4\\cdot 3\\cdot 2 = 0$.\n",
    "\n",
    "---"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Question 2\n",
    "Perform Gaussian elimination to \"fix\" the first columns. I have used only the rule allowing me to add a multiple of a row to a different row, which doesn't change the determinant. We have $\\begin{bmatrix}\n",
    "2&0&1&2&0\\\\\n",
    "0&-1&-1&-1&1\\\\\n",
    "0&0&1&0&3\\\\\n",
    "0&0&3&1&2\\\\\n",
    "0&0&-1&-1&1\n",
    "\\end{bmatrix}$.\n",
    "\n",
    "From here, we can either continue with Gaussian elimination to get our matrix into upper triangular form, then multiply the entries on the diagonal together (remembering to take into account any elementary operations which would change the determinant!), or we can simply compute the determinant of the lower-right $3\\times 3$ matrix, since this is quick to do by hand (it is $-3$). Thus the determinant of the overall matrix is $2\\cdot -1\\cdot -3 = 6$.\n",
    "\n",
    "---"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Question 3\n",
    "### Part a\n",
    "If we solve the equation $\\det(A-\\lambda I) = 0$ for $\\lambda$, we obtain $\\lambda = 1$ only. (Or, indeed, we can observe that $A$ is in lower triangular form, so the eigenvalues are the entries on the main diagonal.)\n",
    "\n",
    "The space $E_1 = \\{x\\in \\mathbb{R}^2 : (A-I)(x)=0\\} = span\\{(0,1)\\}$.\n",
    "\n",
    "### Part b\n",
    "Again, solving $\\det(B-\\lambda I ) = 0$, we find that $\\lambda=2$ or $\\lambda = -3$. We then have $E_2 = span\\{(1,2)\\}$ and $E_{-3} = span\\{ (-2,1) \\}$.\n",
    "\n",
    "---"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Question 4\n",
    "If we take $\\det(A-\\lambda I)$ and simplify, we have $(\\lambda-2)(\\lambda-1)(\\lambda+1)^2$., so we have three eigenvalues. For $\\lambda=2,1$, our eigenspace will certainly have dimension 1. For $\\lambda = -1$, it could (at this stage!) have dimension 1 or 2.\n",
    "\n",
    "Observe that $(1,0,1,1)$ is an eigenvector with eigenvalue 2, and $(1,1,1,1)$ is an eigenvector with eigenvalue 1. Thus $E_2=span\\{(1,0,1,1)\\}$ and $E_1 = span\\{(1,1,1,1)\\}$.\n",
    "\n",
    "Now observe that $rank(A+I)=3$, so there can only be one linearly independent eigenvector with eigenvalue -1. Note that $(0,1,1,0)$ will do. Hence $E_{-1} = span\\{(0,1,1,0)\\}$.\n",
    "\n",
    "---"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Question 5\n",
    "Only the first two are diagonalisable -- they are diagonal, so there is nothing to prove! The other two, however, are not diagonalisable -- each only has one linearly independent eigenvector, whereas we need there to exist a basis of eigenvectors to yield diagonalisability.\n",
    "\n",
    "Only the first and third matrices are invertible -- the determinants are non-zero, while the other two matrices have determinant zero.\n",
    "\n",
    "This tells us that diagonalisability is indeed unrelated to invertibility!\n",
    "\n",
    "---"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Question 6\n",
    "### Part a\n",
    "The characteristic polynomial is $(5-\\lambda)(1-\\lambda)^2$. Now, $rank(A-I) = 2$, so there is only one linearly independent eigenvector for $\\lambda=1$. Hence $A$ is not diagonalisable.\n",
    "\n",
    "We have $E_5 = span\\{(1,1,0)\\}$, and $E_1=span\\{(-3,1,0)\\}$.\n",
    "### Part b\n",
    "The characteristic polynomial here is $-\\lambda^3(1-\\lambda)$, so the eigenvalues are 1, and 0 (with multiplicity 3). Observe that $rank(A-0I) = rank A = 1$, so there are three linearly independent eigenvectors for the eigenvalue 0. With the other eigenvector for $\\lambda=1$, we will have a basis of eigenvectors, and hence $A$ will be diagonalisable.\n",
    "\n",
    "We have $E_1 = span\\{(1,0,0,0)\\}$, and $E_0 = span\\{(1,-1,0,0),(0,0,1,0),(0,0,0,1)\\}$.\n",
    "\n",
    "---"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Question 7\n",
    "### Part a\n",
    "If we form the characteristic polynomial, we have $\\lambda^2-4\\lambda +8$, which has no roots in $\\mathbb{R}$. However, if we extend to $\\mathbb{C}$, then  we will be able to diagonalise the matrix.\n",
    "\n",
    "### Part b\n",
    "This is a symmetric matrix, and is therefore diagonalisable. Its eigenvalues are $3$, and $0$ with multiplicity two, so its diagonal form is $\\begin{bmatrix}\n",
    "3&0&0\\\\\n",
    "0&0&0\\\\\n",
    "0&0&0\n",
    "\\end{bmatrix}$, and a basis of eigenvectors is $\\{(1,1,1),(1,-1,0),(1,0,-1)\\}$.\n",
    "\n",
    "### Part c\n",
    "Here, we have three distinct eigenvalues, and $\\lambda = 4$ has multiplicity two. However, $rank(A-4I) = 3$, so there is only one linearly independent eigenvector, and this $A$ cannot have a basis of eigenvectors, so it is not diagonalisable.\n",
    "\n",
    "### Part d\n",
    "Again here we have two eigenvectors -- $\\lambda=1$ with multiplicity one and $\\lambda=2$ with multiplicity two. However, this time, observe that $rank(A-2I)=1$, so there are indeed two linearly independent eigenvectors for this eigenvalue. Thus $A$ is diagonalisable, with diagonal form $\\begin{bmatrix}\n",
    "1&0&0\\\\\n",
    "0&2&0\\\\\n",
    "0&0&2\n",
    "\\end{bmatrix}$, with eigenvectors $\\{(3,-1,3),(2,1,0),(2,0,1)\\}$.\n",
    "\n",
    "---"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Question 8\n",
    "First, we compute $A^{\\mathsf{T}}A = \\begin{bmatrix}\n",
    "13&12&2\\\\\n",
    "12&13&-2\\\\\n",
    "2&-2&8\n",
    "\\end{bmatrix}$. We can diagonalise this to find $D = \\begin{bmatrix}\n",
    "25&0&0\\\\\n",
    "0&9&0\\\\\n",
    "0&0&0\n",
    "\\end{bmatrix}$ and $P = \\begin{bmatrix}\n",
    "\\frac{1}{\\sqrt2}&\\frac{1}{\\sqrt{18}}&-\\frac23\\\\\n",
    "\\frac{1}{\\sqrt2}&-\\frac{1}{\\sqrt{18}}&\\frac23\\\\\n",
    "0&\\frac{4}{\\sqrt{18}}&\\frac13\n",
    "\\end{bmatrix}$.\n",
    "\n",
    "We take the square roots of the entries of $D$ to find $\\Sigma = \\begin{bmatrix}\n",
    "5&0&0\\\\\n",
    "0&3&0\n",
    "\\end{bmatrix}$, with $V$ equalling our $P$ above.\n",
    "\n",
    "From here, we compute $u_1 = \\frac1{\\sigma_1}Av_1 = \\frac15\\begin{bmatrix}\n",
    "3&2&2\\\\\n",
    "2&3&-2\n",
    "\\end{bmatrix}\n",
    "\\begin{bmatrix}\n",
    "\\frac{1}{\\sqrt2}\\\\\n",
    "\\frac{1}{\\sqrt2}\\\\\n",
    "0\n",
    "\\end{bmatrix} =\n",
    "\\begin{bmatrix}\n",
    "\\frac{1}{\\sqrt2}\\\\\n",
    "\\frac{1}{\\sqrt2}\n",
    "\\end{bmatrix}$, and\n",
    "$u_2 = \\frac{1}{\\sigma_2} A v_2 = \\frac13 \\begin{bmatrix}\n",
    "3&2&2\\\\\n",
    "2&3&-2\n",
    "\\end{bmatrix}\n",
    "\\begin{bmatrix}\n",
    "\\frac{1}{\\sqrt{18}}\\\\-\\frac{1}{\\sqrt{18}}\\\\\n",
    "\\frac{4}{\\sqrt{18}}\n",
    "\\end{bmatrix} =\n",
    "\\begin{bmatrix}\n",
    "\\frac{1}{\\sqrt2}\\\\-\\frac{1}{\\sqrt2}\n",
    "\\end{bmatrix}$, giving $U=\\frac{1}{\\sqrt2}\\begin{bmatrix}\n",
    "1&1\\\\1&-1\n",
    "\\end{bmatrix}$.\n",
    "\n",
    "It can be checked that $A = U\\Sigma V^{\\mathsf{T}}$, indeed!\n",
    "\n",
    "---"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Question 9\n",
    "Observe that the eigenvalues of $A$ are complex, so we cannot simply find the eigendecomposition. Proceeding as in the previous question, we have $A^{\\mathsf{T}}A = \\begin{bmatrix}\n",
    "5&3\\\\\n",
    "3&5\n",
    "\\end{bmatrix}$, which when we perform the eigendecomposition on this new matrix, we obtain $D = \\begin{bmatrix}\n",
    "8&0\\\\\n",
    "0&2\n",
    "\\end{bmatrix}$ and $P=\\frac{1}{\\sqrt2}\\begin{bmatrix}\n",
    "1&-1\\\\\n",
    "1&1\n",
    "\\end{bmatrix}$. This $P$ is again our required $V$, and we have $\\Sigma = \\begin{bmatrix}\n",
    "2\\sqrt2 & 0\\\\\n",
    "0&\\sqrt2\n",
    "\\end{bmatrix}$.\n",
    "\n",
    "As before, we can now compute $u_1 = \\frac{1}{2\\sqrt2}\\begin{bmatrix}\n",
    "2&2\\\\-1&1\n",
    "\\end{bmatrix}\n",
    "\\begin{pmatrix}\n",
    "\\frac{1}{\\sqrt2}\\\\\n",
    "\\frac{1}{\\sqrt2}\n",
    "\\end{pmatrix} = \\begin{bmatrix}\n",
    "1\\\\0\n",
    "\\end{bmatrix}$, and similarly $u_2 = \\begin{bmatrix}\n",
    "0\\\\1\n",
    "\\end{bmatrix}$. Hence, our $U$ turns out to be the identity matrix.\n",
    "\n",
    "---"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Question 10\n",
    "Using our Singular value decomposition from Question 8, we construct $A_1 = \\sigma_1 u_1 v_1^{\\mathsf{T}} = 5 \\begin{bmatrix}\n",
    "\\frac{1}{\\sqrt2}\\\\\n",
    "\\frac{1}{\\sqrt2}\n",
    "\\end{bmatrix}\n",
    "\\begin{bmatrix}\n",
    "\\frac{1}{\\sqrt2}&\\frac{1}{\\sqrt2}&0\n",
    "\\end{bmatrix} =\n",
    "\\frac52 \\begin{bmatrix}\n",
    "1&1&0\\\\\n",
    "1&1&0\n",
    "\\end{bmatrix}$, and similarly $A_2 = \\frac12 \\begin{bmatrix}\n",
    "1&-1&4\\\\-1&1&-4\n",
    "\\end{bmatrix}$. Then $A_1$ and $A_2$ both have rank one, with $A=A_1+A_2$, as required.\n",
    "\n",
    "---"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Question 11\n",
    "We need only show this in one direction, since we can replace $A$ with $A^{\\mathsf{T}}$ below, and the argument still hold true.\n",
    "\n",
    "Suppose $\\lambda\\neq 0$ is an eigenvalue of $A^{\\mathsf{T}}A$. Then there is some vector $x\\neq 0$ such that $A^{\\mathsf{T}}Ax = \\lambda x$. Thus, $AA^{\\mathsf{T}}Ax = \\lambda Ax$. Therefore, $Ax$ (equivalently $\\lambda x$, or, indeed just $x$ itself!)~is an eigenvector of $AA^{\\mathsf{T}}$, with eigenvalue $\\lambda$.\n",
    "\n",
    "---"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Question 12\n",
    "The left hand side describes the largest $\\Vert Ax \\Vert_2$ can be, relative to $\\Vert x \\Vert_2$. That is to say, it represents the biggest scaling that can take place under $A$. If we write $A=U\\Sigma V^{\\mathsf{T}}$, and then note that $U$ and $V^{\\mathsf{T}}$ are both change of basis matrices, we deduce that only $\\Sigma$ is doing any scaling. But $\\Sigma$ is an ``almost diagonal'' matrix, and hence it scales based on its non-zero entries only. Remember that (by convention!)~all the entries on the main diagonal of $\\Sigma$ are non-negative. Hence the largest such value represents the biggest scaling factor, which is the right-hand side of the identity."
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.8.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}
